#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
typedef long long LL;

#define LOCAL

int main() {
#ifdef LOCAL
  ifstream cin("E.in");
  ofstream cout("E.out");
  LL start = clock();
#endif
  ios::sync_with_stdio(false);

#ifdef LOCAL
  LL end = clock();
  cerr << 1.0 * (end - start) / CLOCKS_PER_SEC << endl;
#endif
  return 0;
}
/**
1005 ratio 題解

這份題解將會描述兩種 O(N)O(N)O(N) 解法 。在開始之前，假設讀者已經充分了解：經過
O(N)O(N)O(N) 的 prefix sum 預處理後，可以用 O(1)O(1)O(1)
的時間求出一個起點開始到某個 000 時會取出的值。
解法 A

考慮到給定的值有範圍的限制，累加的和也只會是線性的成長，所以當公比大於 111
或小於 −1-1−1
時，等比級數能維持的長度是有所限制的，因此，我們可以枚舉陣列的每個地方當作起點，暴力找出這個起點可以有多長的等比級數即可。

這個解法中，因為公比為 111 或 −1-1−1
時，還是有可能造成很長的等比數列，因此當我們找了三項後發現公比為 111 或 −1-1−1
的話，就要特別判斷。首先，有一個性質為：只要找到原始陣列中連續的三個
000，也就是輸出陣列中的連續三項，無論首項具體的值是多少，因為第二項減去第一項的差，以及第三項減去第二項的差都是固定的，因此公比也就確定了。因此當我們發現某個起點最長的等比數列超過
333 項、公比為 111 或 −1-1−1 時，原始陣列除了倒數兩個 000
之外，其餘的起點公比也只能是 111 或 −1-1−1，因此可以一併處理掉。
解法 B

相較於解法 A 中枚舉每個起點的做法，我們可以改由枚舉第一個 000
的位置再往前找合適的起點有幾個。

延續上面觀察到的性質 (只要找到原始陣列中連續的三個
000，也就是輸出陣列中的連續三項，公比就確定了)。我們可以發現兩個不同公比的最長等比數列最多只會重疊兩項，因此可以對於每個可能的連續三個
000，我們都可以把公比算出來，並且往後找到同公比最長可以延伸到的位置，再這個區間中暴力的找有幾個起點可以滿足要求。算完一個區間後，我們只要把起點放到此區間的倒數第二個
000 再找新的區間即可。

因為這些區間彼此最多只會相交兩項，所以最多只會有 O(N)O(N)O(N)
個區間，這些區間的長度總和也只會是 O(N)O(N)O(N)。所以整體時間複雜度也會是
O(N)O(N)O(N)。這個解法比較麻煩的點是可能要另外計算長度為 111 跟 222 的等比數列。
固定三項間的差，求公比

假定 prefix sum 中對於真實首項的 offset 為 β\betaβ，令 prefix sum
中三項的值分別為 v1=x+βv_1 = x + \betav​1​​=x+β, v2=αx+βv_2 = \alpha x +
\betav​2​​=αx+β, v3=α2x+βv_3 = \alpha^2 x +
\betav​3​​=α​2​​x+β，而已知的差為 A=v2−v1=x(α−1)A = v_2 - v_1 =
x(\alpha -1)A=v​2​​−v​1​​=x(α−1) 跟 B=v3−v2=xα(α−1)B = v_3 - v_2 =
x\alpha(\alpha - 1)B=v​3​​−v​2​​=xα(α−1)，因此公比 α\alphaα 即為
B/AB/AB/A。要注意的是，如果A=B=0A=B=0A=B=0 則公比為 111，如果 AAA 跟 BBB
中恰有一項為 000，那這三項 (v1v_1v​1​​, v2v_2v​2​​,
v3v_3v​3​​) 不構成本題合法的等比數列。

整體時間複雜度為 O(N)O(N)O(N)。
*/